More Structural Characterizations of Some Subregular Language Families by Biautomata
We study structural restrictions on biautomata such as, e.g., acyclicity, permutation-freeness, strongly permutation-freeness, and orderability, to mention a few. We compare the obtained language families with those induced by deterministic finite automata with the same property. In some cases, it i...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Open Publishing Association
2014-05-01
|
| Series: | Electronic Proceedings in Theoretical Computer Science |
| Online Access: | http://arxiv.org/pdf/1405.5608v1 |
| _version_ | 1819211790438891520 |
|---|---|
| author | Markus Holzer Sebastian Jakobi |
| author_facet | Markus Holzer Sebastian Jakobi |
| author_sort | Markus Holzer |
| collection | DOAJ |
| description | We study structural restrictions on biautomata such as, e.g., acyclicity, permutation-freeness, strongly permutation-freeness, and orderability, to mention a few. We compare the obtained language families with those induced by deterministic finite automata with the same property. In some cases, it is shown that there is no difference in characterization between deterministic finite automata and biautomata as for the permutation-freeness, but there are also other cases, where it makes a big difference whether one considers deterministic finite automata or biautomata. This is, for instance, the case when comparing strongly permutation-freeness, which results in the family of definite language for deterministic finite automata, while biautomata induce the family of finite and co-finite languages. The obtained results nicely fall into the known landscape on classical language families. |
| first_indexed | 2024-12-23T06:32:40Z |
| format | Article |
| id | doaj.art-d0ec80a6fa0f4e89bd3955773e44368e |
| institution | Directory Open Access Journal |
| issn | 2075-2180 |
| language | English |
| last_indexed | 2024-12-23T06:32:40Z |
| publishDate | 2014-05-01 |
| publisher | Open Publishing Association |
| record_format | Article |
| series | Electronic Proceedings in Theoretical Computer Science |
| spelling | doaj.art-d0ec80a6fa0f4e89bd3955773e44368e2022-12-21T17:56:54ZengOpen Publishing AssociationElectronic Proceedings in Theoretical Computer Science2075-21802014-05-01151Proc. AFL 201427128510.4204/EPTCS.151.19:30More Structural Characterizations of Some Subregular Language Families by BiautomataMarkus HolzerSebastian JakobiWe study structural restrictions on biautomata such as, e.g., acyclicity, permutation-freeness, strongly permutation-freeness, and orderability, to mention a few. We compare the obtained language families with those induced by deterministic finite automata with the same property. In some cases, it is shown that there is no difference in characterization between deterministic finite automata and biautomata as for the permutation-freeness, but there are also other cases, where it makes a big difference whether one considers deterministic finite automata or biautomata. This is, for instance, the case when comparing strongly permutation-freeness, which results in the family of definite language for deterministic finite automata, while biautomata induce the family of finite and co-finite languages. The obtained results nicely fall into the known landscape on classical language families.http://arxiv.org/pdf/1405.5608v1 |
| spellingShingle | Markus Holzer Sebastian Jakobi More Structural Characterizations of Some Subregular Language Families by Biautomata Electronic Proceedings in Theoretical Computer Science |
| title | More Structural Characterizations of Some Subregular Language Families by Biautomata |
| title_full | More Structural Characterizations of Some Subregular Language Families by Biautomata |
| title_fullStr | More Structural Characterizations of Some Subregular Language Families by Biautomata |
| title_full_unstemmed | More Structural Characterizations of Some Subregular Language Families by Biautomata |
| title_short | More Structural Characterizations of Some Subregular Language Families by Biautomata |
| title_sort | more structural characterizations of some subregular language families by biautomata |
| url | http://arxiv.org/pdf/1405.5608v1 |
| work_keys_str_mv | AT markusholzer morestructuralcharacterizationsofsomesubregularlanguagefamiliesbybiautomata AT sebastianjakobi morestructuralcharacterizationsofsomesubregularlanguagefamiliesbybiautomata |