Search

Complex frameworks for defining programming languages aim to generate various tools (e.g. interpreters, symbolic execution engines, deductive verifiers, etc.) using only the formal definition of a language. When used at an industrial scale, these tools are constantly updated, and at the same time, it is required to be trustworthy. Ensuring the correctness of such a framework is practically impossible. A solution is to generate proof objects as correctness artefacts that can be checked by an external trusted checker. A logic suitable for developing such frameworks is matching logic. K framework is a canonical example having matching logic-based foundation. Since the (symbolic) configurations of the programs are represented by matching logic patterns, the algorithms computing the dynamics of these configurations can be seen as pattern transformers and a proof object should be generated for the relationship between these patterns. In this paper, we show that conjunctions and disjunctions of patterns, produced by semantics or analysis rules, can be safely normalized using unification and antiunification algorithms. We also provide a prototype implementation of our proof object generation technique and a checker for certifying the generated objects. [ABSTRACT FROM AUTHOR]

This paper focuses on the formal semantics of programming languages, with a specific focus on Domain-Specific Languages (DSLs). It introduces the Robot DSL, characterized by total semantic functions, an infinite network size, and an obstacle-free environment. The study explores denotational and natural semantics, aiming to define and prove their equivalence. This work contributes to the understanding of programming languages with unique features, laying the groundwork for future developments in language design and formal semantics. [ABSTRACT FROM AUTHOR]

This paper proposes an interpretable geometry solution based on the formal language set of text and diagram. Geometry problems are solved using machines; however, machines encounter challenges in natural language processing and computer vision. Significant progress has improved existing methods in the extraction of geometric formal languages. However, the neglect of the graph structure information in the formal language and the lack of further refinement of the extracted language set can lead to poor theorem prediction and poor accuracy in problem solving. In this paper, a formal language graph is constructed using the extracted formal language set and applied to theorem prediction using a graph convolutional network. To better extract the relationship set of diagram elements, an improved diagram parser is proposed. The test results indicate that the improved method has good results when solving interpretable geometry problems. [ABSTRACT FROM AUTHOR]

A classic result in formal language theory is the equivalence among noncounting, or aperiodic, regular languages, and languages defined through star-free regular expressions, or first-order logic. Past attempts to extend this result beyond the realm of regular languages have met with difficulties: for instance it is known that star-free tree languages may violate the non-counting property and there are aperiodic tree languages that cannot be defined through first-order logic. We extend such classic equivalence results to a significant family of deterministic contextfree languages, the operator-precedence languages (OPL), which strictly includes the widely investigated visibly pushdown, alias input-driven, family and other structured context-free languages. The OP model originated in the '60s for defining programming languages and is still used by high performance compilers; its rich algebraic properties have been investigated initially in connection with grammar learning and recently completed with further closure properties and with monadic second order logic definition. We introduce an extension of regular expressions, the OP-expressions (OPE) which define the OPLs and, under the star-free hypothesis, define first-order definable and non-counting OPLs. Then, we prove, through a fairly articulated grammar transformation, that aperiodic OPLs are first-order definable. Thus, the classic equivalence of star-freeness, aperiodicity, and first-order definability is established for the large and powerful class of OPLs. We argue that the same approach can be exploited to obtain analogous results for visibly pushdown languages too. [ABSTRACT FROM AUTHOR]

This paper analyzes a new distinguishability operation for finite deterministic machines and languages. The research was inspired by the "Gedanken experiments" on sequential machines performed by Moore in 1956, and extends the study of the unary distinguishability operation to a binary one. Besides studying the new operation's properties, we give a tight bound of its state complexity on regular languages, including the case for finite languages. • We introduce a new binary operation on languages and finite state machines. • We compute the state complexity of this operation for deterministic machines. • The case of incomplete machines and finite languages is also studied. • We prove several properties of the set of minimal distinguishable words. • We improve the results by Moore, and by Shallit for minimal distinguishable words. [ABSTRACT FROM AUTHOR]

Compiler correctness, in its simplest form, is defined as the inclusion of the set of traces of the compiled program in the set of traces of the original program. This is equivalent to the preservation of all trace properties. Here, traces collect, for instance, the externally observable events of each execution. However, this definition requires the set of traces of the source and target languages to be the same, which is not the case when the languages are far apart or when observations are fine-grained. To overcome this issue, we study a generalized compiler correctness definition, which uses source and target traces drawn frompotentially different sets and connected by an arbitrary relation. We set out to understand what guarantees this generalized compiler correctness definition gives us when instantiated with a non-trivial relation on traces. When this trace relation is not equality, it is no longer possible to preserve the trace properties of the source program unchanged. Instead, we provide a generic characterization of the target trace property ensured by correctly compiling a program that satisfies a given source property, and dually, of the source trace property one is required to show to obtain a certain target property for the compiled code. We show that this view on compiler correctness can naturally account for undefined behavior, resource exhaustion, different source and target values, side channels, and various abstraction mismatches. Finally, we show that the same generalization also applies to many definitions of secure compilation, which characterize the protection of a compiled program linked against adversarial code. [ABSTRACT FROM AUTHOR]

This paper presents the framework for the creation of various domain-specific languages for verification of the functional requirements. When it comes to Requirement Engineering and the process of Validation and Verification of the requirements, there are plenty of tools for modeling, analyzing, and validating the requirements. It comes as a fullblown set of applications for validation of the requirements. But the set of the verification tools is either too complex or usable in a narrow domain. From the customers' point of view, there is a need for another independent requirement verification. This tool enables the creation of the custom verification in a way that allows users (either clients or developers) to verify requirements. It follows the IEEE guides, standards, and best practices to check all aspects of the software requirements that are neither implemented nor checked by the validation process: correctness, completeness, traceability, dependency, importance, and uniqueness. Tool implements design patterns specific to the verification process, thus enabling the faster implementation of the language. The concept can be used for development of the verification-specific language with any type of requirement representation, which will be shown by a few examples. [ABSTRACT FROM AUTHOR]

Security-preserving compilers generate compiled code that withstands target-level attacks such as alteration of control flow, data leaks, or memory corruption. Many existing security-preserving compilers are proven to be fully abstract, meaning that they reflect and preserve observational equivalence. Fully abstract compilation is strong and useful but, in certain cases, comes at the cost of requiring expensive runtime constructs in compiled code. These constructs may have no relevance for security, but are needed to accommodate differences between the source and target languages that fully abstract compilation necessarily needs. As an alternative to fully abstract compilation, this article explores a different criterion for secure compilation called robustly safe compilation or RSC. Briefly, this criterion means that the compiled code preserves relevant safety properties of the source program against all adversarial contexts interacting with the compiled program. We show that RSC can be proved more easily than fully abstract compilation and also often results in more efficient code. We also present two different proof techniques for establishing that a compiler attains RSC and, to illustrate them, develop three illustrative robustly safe compilers that rely on different target-level protection mechanisms. We then proceed to turn one of our compilers into a fully abstract one and through this example argue that proving RSC can be simpler than proving full abstraction. [ABSTRACT FROM AUTHOR]

Atomic polymorphism |$\mathbf{F_{at}}$| is a restriction of Girard and Reynold's system |$\mathbf{F} $| (or |$\lambda 2$|⁠) which was first introduced in Ferreira [ 2 ] in the context of a philosophical commentary on predicativism. |$\lambda 2$| is a well-known and powerful formal tool for studying polymorphic functional programming languages and formal methods in program specification and development, but its computational power far exceeds the recursive level of interest in applications. Hence, the interest of studying subsystems of |$\lambda 2$| with weaker computational power. |$\mathbf{F_{at}}$| is defined by restricting instantiation to atomic variables only. It turns out that the type system is still sufficiently powerful to possess embeddings of full intuitionistic propositional calculus [ 3 , 4 ], and since the calculus has fewer connectives and strong normalizability is simple to prove [ 3 ], this result allows us to circumvent many of the extra computational complexities present when dealing with the proof theory of IPC. It is natural to inquire whether type inhabitation, i.e. provability in the corresponding fragment of second-order intuitionistic propositional logic, is decidable or not and in general to see whether the negative results involving the undecidability of type inhabitation, typability and type-checking for |$\mathbf{F}$| still hold in this fragment. A further theme would be to study the result of adding type constructors, recursors or even dependent types to |$\mathbf{F_{at}}$|⁠. In this paper, we show that type inhabitation for |$\mathbf{F_{at}}$| is undecidable by codifying within it an undecidable fragment of first-order intuitionistic predicate calculus, adapting and modifying the technique of Urzyczyn's [ 1 , 7 ] purely syntactic proof of the undecidability of type inhabitation for |$\mathbf{F}$|⁠. [ABSTRACT FROM AUTHOR]

Aims: The machine‐readable formal language of classification expert systems has become a standard for applying plot assignment rules in vegetation classification. Here we present an efficient algorithm implementing the vegetation classification expert system in the statistical programming language R. Methods: The principal idea of the R implementation is to solve the assignments to vegetation types not sequentially plot by plot but to parse the assignment rules into (nested) components that each can be evaluated by simultaneous vector‐based processing of all plots in a database. Results and conclusions: We demonstrate the algorithm taking the EUNIS classification expert system of European habitat types (EUNIS‐ESy) as an example. The R code version of the vegetation classification expert system is particularly useful in large vegetation‐plot databases because it solves all logical operations vector‐wise across all plots, allowing for efficient evaluation of membership expressions and formulas. Another advantage of the R implementation is that membership formulas are not only readable but can also be produced as a machine‐written result, for example as the output of classification algorithms run in R. [ABSTRACT FROM AUTHOR]

The security of blockchain smart contracts is one of the most emerging issues of the greatest interest for researchers. This article presents an intermediate specification language for the formal verification of Ethereum-based smart contract in Coq, denoted as Lolisa. The formal syntax and semantics of Lolisa contain a large subset of the Solidity programming language developed for the Ethereum blockchain platform. To enhance type safety, the formal syntax of Lolisa adopts a stronger static type system than Solidity. In addition, Lolisa includes a large subset of Solidity syntax components as well as general-purpose programming language features. Therefore, Solidity programs can be directly translated into Lolisa with line-by-line correspondence. Lolisa is inherently generalizable and can be extended to express other programming languages. Finally, the syntax and semantics of Lolisa have been encapsulated as an interpreter in mathematical tool Coq. Hence, smart contracts written in Lolisa can be symbolically executed and verified in Coq. [ABSTRACT FROM AUTHOR]

In this article, we present a new version of the language of Epistemic Specifications. The goal is to simplify and improve the intuitive and formal semantics of the language. We describe an algorithm for computing solutions of programs written in this new version of the language. The new semantics is illustrated by a number of examples, including an Epistemic Specifications-based framework for conformant planning. In addition, we introduce the notion of an epistemic logic program with sorts. This extends recent efforts to define a logic programming language that includes the means for explicitly specifying the domains of predicate parameters. An algorithm and its implementation as a solver for epistemic logic programs with sorts is also discussed. [ABSTRACT FROM AUTHOR]

In order to define executable hardware description language while at the same time be fit for formal proofs of properties, a hardware description language VeriFormal, embedded in Isabelle/HOL, was created. VeriFormal, together with a translator and Isabelle/HOL proof facility, provides a platform for designing, simulating and reasoning about hardware designs. Building such an environment is challenging due to the fact that the designer must have expertise in programming language design, the specific domain and theorem prover. It requires selection of a language design criteria, host language, grammar, embedding approach and techniques and mechanisms to address determinism and termination issues. When the language in question is a hardware description language, it requires specialized treatment of events, their scheduling, data types and assignments. In this paper, we report on our experience of embedding hardware description language VeriFormal in theorem prover Isabelle/HOL. In particular, the structure and execution of programs in the context of theorem provers and their impact on the overall language design are discussed. Among the main features of VeriFormal include formal semantics of the language, support for mechanical reasoning about designs and compiler and type checking of modules using Isabelle/HOL as well as VeriFormal type checkers. [ABSTRACT FROM AUTHOR]

Featured Application: A general-purpose naturalistic language can be used to develop software systems using a syntax closer to natural languages, but formal enough to avoid ambiguity. This is useful for tasks such as requirement transformation, maintenance and software evolution. While the use of natural language for software development has been proposed since the 1960s, it was limited by the inherent ambiguity of natural languages, which people resolve using reasoning in a text or conversation. Programming languages are formal general-purpose or domain-specific alternatives based on mathematical formalism and which are at a remove from natural language. Over the years, various authors have presented studies in which they attempted to use a subset of the English language for solving particular problems. Each author approached the problem by covering particular domains, rather than focusing on describing general elements that would help other authors develop general-purpose languages, instead focusing even more on domain-specific languages. The identification of common elements in these studies reveals characteristics that enable the design and implementation of general-purpose naturalistic languages, which requires the establishment of a programming model. This article presents a conceptual model which describes the elements required for designing general-purpose programming languages and which integrates abstraction, temporal elements and indirect references into its grammar. Moreover, as its grammar resembles natural language, thus reducing the gap between problem and solution domains, a naturalistic language prototype is presented, as are three test scenarios which demonstrate its characteristics. [ABSTRACT FROM AUTHOR]

Among model checking tools, the behaviour of a system is often formalized as a transition system with atomic propositions associated with states (Kripke structure). In current modeling languages, transitions are usually specified as updates of the system's variables to be performed when certain conditions are satisfied. However, such a low-level representation makes the description of complex transformations difficult, in particular in the presence of structured data. We present Objective/MC, a high-level language with imperative semantics for modeling finite-state systems. The language features are selected with the aim of enabling the translation of models into compact transition systems, amenable to efficient verification via model checking. To this end, we have developed a compiler of our high-level language into the modeling language of the PRISM probabilistic model checker. One of the main characteristics of the language is that it makes a very different treatment of global and local variables. It is assumed that global variables are actually the variables that describe the state of the modeled system, whereas local variables are only used to ease the specification of the system's internal mechanisms. In this paper, we give a complete formal definition of the language, its type system and static analyses, of the transformations to be performed at the level of the Control Flow Graph for the pruning of local variables, and of the PRISM code generation. [ABSTRACT FROM AUTHOR]

Let Σ be an alphabet having at least three symbols. Let C F L denote the family of all context-free languages over Σ , P E G denote the family of all parsing expression grammars over Σ , and P E L denote the family of all parsing expression languages over Σ. Let K satisfy K ⊆ C F L and " K ∩ P E L ≠ ∅ ", where we use the double-quoted " K ∩ P E L ≠ ∅ " in the sense that we can effectively find some G ∈ P E G such that L (G) ∈ K ∩ P E L. Then the following problem is shown to be undecidable: Given G ∈ P E G , decide if L (G) ∈ K. In particular, the following basic problem is shown to be undecidable: Given G ∈ P E G , decide if L (G) ∈ C F L. [ABSTRACT FROM AUTHOR]

A pseudoknot is a crucial intra-molecular structure formed primarily in RNA strands and closely related to important biological processes. This motivates us to define an operation that generates all pseudoknots from a given sequence and consider algorithmic and language theoretic properties of the operation. We design an efficient algorithm that decides whether or not a given string is a pseudoknot of a regular language L . Our algorithm runs in linear time if L is given by a deterministic finite automaton. We study closure and decision properties of the pseudoknot-generating operation. For DNA encoding applications, pseudoknot structures are undesirable. We give polynomial-time algorithms that check whether or not a regular language L contains a pseudoknot or a pseudoknot generated by some string of L . Furthermore, we show that the corresponding questions for context-free languages are undecidable. [ABSTRACT FROM AUTHOR]

We establish the relation between two language recognition models that use counters and operate in real-time: Greibach's partially blind machines operating in real time (RT-PBLIND), which recognize Petri Net languages, and the consensually regular (CREG) language model of the authors. The latter is based on synchronized computational threads of a finite automaton, where at each step one thread acts as the leader and all other threads as followers. We introduce two new normal forms of RT-PBLIND machines (and Petri Nets), such that counter operations are scheduled and rarefied, and transitions are quasi-deterministic, i.e., the finite automaton obtained by eliminating counter moves is deterministic. We prove that the CREG family can simulate any normalized RT-PBLIND machine, but it also contains the non-RT-PBLIND language { a n b n | n > 1 } ⁎ . [ABSTRACT FROM AUTHOR]

The paper tries to put together one computer languages view on Battle Management Languages (BMLs) with the current C-BML Phase 1 Standard: We present a case study on creating language representations by means of formal parsable context-free grammars and corresponding language processors in the area of military C2 systems utilizing the standardized C-BML data structures. We point out how techniques and tools previously used in the area of compilers (namely Flex, Bison) are exploitable in the military domain and thus might be helpful in integration of national command and control systems and deployment in multinational environment. We start with an introduction to C-BML principles and data model; next we describe the basis for our (Slovak) language representation followed by its specification in the form of a parsable context-free grammar; next follows the section devoted to the lexical, syntactic, and semantic processing of the language representation with the utilisation of Flex and Bison tools. [ABSTRACT FROM AUTHOR]

This paper establishes two new normal forms for phrase-structure grammars in which both contextfree rules and non-context-free rules are in prescribed forms. In addition, a limit is placed on the number of context-free rules. More specifically, the first form has 2 + n context-free rules, where n is the number of terminals. Concerning non-context-free rules, each of them has the form AB → CD, where A, B, C,Dare nonterminals. The second normal form has always only two context-free rules--S → S# and # → ε, where S is the start symbol, # is a nonterminal, and εis the empty string. Regarding noncontext- free rules, each of them is of the form AB → XD, where A,B,D are nonterminals and X is a nonterminal or a terminal. [ABSTRACT FROM AUTHOR]

A (factor-)reference in a word is a special symbol that refers to another factor in the same word; a reference is dereferenced by substituting it with the referenced factor. We introduce and investigate the class ref-REG of all languages that can be obtained by taking a regular language R and then dereferencing all possible references in the words of R . We show that ref-REG coincides with the class of languages defined by regular expressions as they exist in modern programming languages like Perl, Python, Java, etc. (often called REGEX languages). [ABSTRACT FROM AUTHOR]

This paper proposes English to Tamil machine translation system, using the universal networking language (UNL) as the intermediate representation. The UNL approach is a hybrid approach of the rule and knowledge-based approaches to machine translation. UNL is a declarative formal language, specifically designed to represent semantic data extracted from a natural language text. The input English sentence is converted to UNL (enconversion), which is then converted to a Tamil sentence (deconversion) by ensuring that the meaning of the input sentence is preserved. The representation of UNL was modified to suit the translation process. A new sentence formation algorithm was also proposed to rearrange the translated Tamil words to sentences. The translation system was evaluated using bilingual evaluation understudy (BLEU) score. A BLEU score of 0.581 was achieved, which is an indication that most of the information in the input sentence is retained in the translated sentence. The scores obtained using the UNL based approach were compared with existing approaches to translation, and it can be concluded that the UNL is a more suited approach to machine translation. [ABSTRACT FROM AUTHOR]

An increasing number of applications in verification and security rely on or could benefit from automatic solvers that can check the satisfiability of constraints over a diverse set of data types that includes character strings. Until recently, satisfiability solvers for strings were standalone tools that could reason only about fairly restricted fragments of the theory of strings and regular expressions (e.g., strings of bounded lengths). These solvers were based on reductions to satisfiability problems over other data types such as bit vectors or to automata decision problems. We present a set of algebraic techniques for solving constraints over a rich theory of unbounded strings natively, without reduction to other problems. These techniques can be used to integrate string reasoning into general, multi-theory SMT solvers based on the common DPLL( T) architecture. We have implemented them in our SMT solver cvc4, expanding its already large set of built-in theories to include a theory of strings with concatenation, length, and membership in regular languages. This implementation makes cvc4 the first solver able to accept a rich set of mixed constraints over strings, integers, reals, arrays and algebraic datatypes. Our initial experimental results show that, in addition, on pure string problems cvc4 is highly competitive with specialized string solvers accepting a comparable input language. [ABSTRACT FROM AUTHOR]

Numerical P systems are a class of P systems inspired both from the structure of living cells and from economics. In this work, we further investigate the generative capacity of numerical P systems as language generators. The families of languages generated by non-enzymatic, by enzymatic, and by purely enzymatic (all programs are enzymatic) numerical P systems working in the sequential mode are compared with the language families in the Chomsky hierarchy. Especially, a characterization of recursively enumerable languages is obtained by using purely enzymatic numerical P systems working in the sequential mode. [ABSTRACT FROM AUTHOR]

Linear conjunctive grammars define the same family of languages as one-way real-time cellular automata (A. Okhotin, “On the equivalence of linear conjunctive grammars to trellis automata”, RAIRO ITA , 2004), and this family is known to be incomparable with the context-free languages (V. Terrier, “On real-time one-way cellular array”, Theoret. Comput. Sci. , 1995). This paper demonstrates the containment of the languages accepted by input-driven pushdown automata (a.k.a. visibly pushdown automata) in the family of linear conjunctive languages, which is established by a direct simulation of an input-driven automaton by a one-way real-time cellular automaton. On the other hand, it is shown that the language families defined by the unambiguous grammars, the LR ( k ) grammars and the LL ( k ) grammars are incomparable with the linear conjunctive languages. [ABSTRACT FROM AUTHOR]

Idempotency languages are generated from a single word by iterated application of rules of the form for natural numbers m and n. We investigate these languages over alphabets of only one or two letters. The conditions under which the underlying rewrite relations are confluent are fully characterized. Then for many combinations of the parameters m and n we answer the question, whether the corresponding idempotency languages are regular or not. What remains open are only the cases where . [ABSTRACT FROM AUTHOR]

In this paper we examine subshifts from the perspective of formal languages. Several classes of languages of subshifts are shown to be closed under (dynamical) factor maps. The main theorem is inspired by and extends the well known result that the class of sofic shifts is closed under factoring. [ABSTRACT FROM AUTHOR]

Given a string, a non-overlapping inversion is to reverse some non-overlapping fragments of the string simultaneously. We define a non-overlapping inversion operation to be the computation of all possible non-overlapping inversions. We apply the operation on a string, which gives rise to a set of strings, and construct an NFA recognizing the set. Then, we design an efficient DFA reduction algorithm from the resulting NFA. We also consider the non-overlapping inversion operation on a language and show the closure properties for regular, context-free and context-sensitive languages. We furthermore examine iterative non-overlapping inversions and establish the closure properties. Finally, we introduce non-overlapping inversion-free languages and present the decidability results for regular and context-free languages. [ABSTRACT FROM AUTHOR]

Adaptable Parsing Expression Grammar (APEG) is a formal method for defining the syntax of programming languages. It provides an on-the-fly mechanism to perform modifications of the syntax of the language during parsing time. The primary goal of this dynamic mechanism is the formal specification and the automatic parser generation for extensible languages. In this paper, we show how APEG can be used for the definition of the extensible languages SugarJ and Fortress, clarifying many aspects of the syntax of these languages. We also show that the mechanism for on-the-fly modification of syntax rules can be useful for defining grammars in a modular way, implementing almost all types of language composition in the context of specification of extensible languages. [ABSTRACT FROM AUTHOR]

The paper introduces node replacement graph grammars with dynamic node relabeling as an extension of the eNCE families of graph grammars. Initiated by NLC grammars in which graph embedding is based on node labels only, node distinction of the embedded graph extended NLC grammars to NCE grammars and dynamic edge relabeling further extended NCE grammars to eNCE grammars. Now, dynamic node relabeling, the node counterpart of the dynamic edge relabeling, is introduced as the next extension, which we call neNCE. The paper analyzes basic language-theoretical properties of the neNCE system. [ABSTRACT FROM AUTHOR]

In order to tackle the ambiguities of geometrical product specification (GPS), GeoSpelling language has been developed to express the semantics of specifications. A detailed syntax of GeoSpelling is proposed in this paper. A specification is defined as a sequence of operations on the skin model. The syntax is based on instructions used in computer programming language: call to functions and flow control by condition and loop. In GeoSpelling, the call to functions corresponds to the declaration of operations; loops make it possible to manage a set of features with rigor and conditions to select features from a set. [ABSTRACT FROM AUTHOR]

Recently, Dassow et al. connected partial words and regular languages. Partial words are sequences in which some positions may be undefined, represented with a “hole” symbol ⋄. If we restrict what the symbol ⋄ can represent, we can use partial words to compress the representation of regular languages. Doing so allows the creation of so-called ⋄-DFAs, smaller than the DFAs recognizing the original language L , which recognize the compressed language. However, the ⋄-DFAs may be larger than the NFAs recognizing L . In this paper, we investigate a question of Dassow et al. as to how these sizes are related. [ABSTRACT FROM AUTHOR]

Limited automata are one-tape Turing machines which are allowed to rewrite each tape cell only in the first d visits, for a given constant d. For each d ≥⃒ 2, these devices characterize the class of context-free languages. We investigate the equivalence between 2-limited automata and pushdown automata, comparing the relative sizes of their descriptions. We prove exponential upper and lower bounds for the sizes of pushdown automata simulating 2-limited automata. In the case of the conversion of deterministic 2-limited automata into deterministic pushdown automata the upper bound is double exponential and we conjecture that it cannot be reduced. On the other hand, from pushdown automata we can obtain equivalent 2-limited automata of polynomial size, also preserving determinism. From our results, it follows that the class of languages accepted by deterministic 2-limited automata coincides with the class of deterministic context-free languages. [ABSTRACT FROM AUTHOR]

In this paper, we approach the problem of accepting all recursively enumerable languages by accepting networks of evolutionary processors (ANEPs, for short) with a fixed architecture. More precisely, we show that every recursively enumerable language can be accepted by an ANEP with an underlying graph in the form of a star with 13 nodes or by an ANEP with an underlying grid with 13 × 4 = 52 nodes as well as by ANEPs having underlying graphs in the form of a chain, a ring, or a wheel with 29 nodes each. In all these cases, the size and form as well as the general working strategy of the constructed networks do not depend on the accepted language; only the rewriting rules and the filters associated to each node of the networks depend on this language. Noteworthy is also the fact that the filtering process is implemented using random context conditions only. Our results answer problems which were left open in a paper published by J. Dassow and F. Manea at the conference on Descriptional Complexity of Formal Systems (DCFS) 2010 and improve a result published by B. Truthe at the conference on Non-Classical Models of Automata and Applications (NCMA) 2013. [ABSTRACT FROM AUTHOR]

In this paper we describe a sound, but not complete, analysis to prove the termination of higher-order attribute grammar evaluation caused by the creation of an unbounded number of (finite) trees as local tree-valued attributes, which are then themselves decorated with attributes. The analysis extracts a set of term-rewriting rules from the grammar that model creation of new syntax trees during the evaluation of higher-order attributes. If this term rewriting system terminates, then only a finite number of trees will be created during attribute grammar evaluation. The analysis places an ordering on nonterminals to handle the cases in which higher-order inherited attributes are used to ensure that a finite number of trees are created using such attributes. When paired with the traditional completeness and circularity analyses for attribute grammars and the assumption that each attribute equation defines a terminating computation, this analysis can be used to show that attribute grammar evaluation will terminate normally. This analysis can be applied to a wide range of common attribute grammar idioms and has been used to show that evaluation of our specification of Java 1.4 terminates. We also describe a modular version of the analysis that is performed on independently developed language extension grammars and the host language being extended. If the extensions individually pass the modular analysis then their composition is also guaranteed to terminate. [ABSTRACT FROM AUTHOR]

Abstract: We introduce the polynomial-time tree reducibility (ptt-reducibility) for formal languages. Our main result establishes a one–one correspondence between this reducibility and inclusions between complexity classes. More precisely, for languages B and C it holds that B ptt-reduces to C if and only if the unbalanced leaf-language class of B is robustly contained in the unbalanced leaf-language class of C. Formerly, such correspondence was only known for balanced leaf-language classes. Moreover, we show that restricted to regular languages, the levels 0, 1/2, 1, and 3/2 of the dot-depth hierarchy are closed under ptt-reducibility. Our results also have applications in complexity theory: We obtain the first gap theorem of leaf-language definability above the Boolean closure of NP. [Copyright &y& Elsevier]

Limited automata are one-tape Turing machines that are allowed to rewrite the content of any tape cell only in the first d visits, for a fixed constant d. In the case d = 1, namely, when a rewriting is possible only during the first visit to a cell, these models have the same power of finite state automata. We prove state upper and lower bounds for the conversion of 1-limited automata into finite state automata. In particular, we prove a double exponential state gap between nondeterministic 1-limited automata and one-way deterministic finite automata. The gap reduces to a single exponential in the case of deterministic 1-limited automata. This also implies an exponential state gap between nondeterministic and deterministic 1-limited automata. Another consequence is that 1-limited automata can have less states than equivalent two-way nondeterministic finite automata. We show that this is true even if we restrict to the case of the one-letter input alphabet. For each d ≥ 2, d-limited automata are known to characterize the class of context-free languages. Using the Chomsky-Schützenberger representation for contextfree languages, we present a new conversion from context-free languages into 2-limited automata. [ABSTRACT FROM AUTHOR]

The avoidability of binary patterns by binary cube-free words is investigated and the exact bound between unavoidable and avoidable patterns is found. All avoidable patterns are shown to be D0L-avoidable. For avoidable patterns, the growth rates of the avoiding languages are studied. All such languages, except for the overlap-free language, are proved to have exponential growth. The exact growth rates of languages avoiding minimal avoidable patterns are approximated through computer-assisted upper bounds. Finally, a new example of a pattern-avoiding language of polynomial growth is given. [ABSTRACT FROM PUBLISHER]